package com.yayako.main.struc;

import java.util.HashMap;
import java.util.Stack;

/**
 * NFA类
 *
 * @author cyy
 */
public class NFA {
    /** 对应的正规式 */
    private String regex;
    /** 初态 */
    private int s0;
    /** 终态 */
    private int f;
    /** NFA图 */
    private Digraph digraph;

    public NFA(String regex) {
        this.regex = regex;
        regex = initial(regex); // 初始化正规式，方便构造nfa

        char[] chars = regex.toCharArray();
        int n = chars.length - 1;
        digraph = new Digraph(n + 1);

        Stack<Integer> stack = new Stack<>(); // 记录 '('、'|' 对应下标
        Stack<Integer> stackForOr = new Stack<>();
        HashMap<Integer, Integer> memo = new HashMap<>(); // k-v: 字符下标-状态号

        char cur; // 正规式当前字符
        int leftBracket = 0; // 左括号下标
        int outLeftBracket; // 记录 '|' 的外层左括号对应状态号

        // i代表当前状态号，j代表正规式字符下标
        for (int i = 0, j = 0; j < n; ++i, ++j) {
            memo.put(j, i);
            cur = chars[j];

            if (cur == '(') {
                stack.push(j);
                stackForOr.push(i);

            } else if (cur == '|') {
                stack.push(j);

            } else if (cur == ')') {

                int ori, or; // |
                outLeftBracket = stackForOr.pop();
                while (chars[(or = stack.pop())] == '|') {
                    ori = memo.get(or);
                    digraph.addEdge(outLeftBracket, ori + 1);
                    digraph.addEdge(ori, i + 1);
                    f = Math.max(f, i + 1);
                }
                leftBracket = memo.get(or);
            }

            // 连接节点
            if (i < n && cur != '|' && cur != '*') {
                if (cur == '(' || cur == ')') {
                    digraph.addEdge(i, i + 1);
                } else {
                    digraph.addEdge(i, i + 1, cur);
                }
                f = Math.max(f, i + 1);
            }

            // 匹配 '*'
            if (chars[j + 1] == '*') {
                digraph.addEdge(i, leftBracket + 1);
                digraph.addEdge(leftBracket, i + 1);
                f = Math.max(f, i + 1);
                // '*'已经匹配，跳过，以及*结尾的情况直接跳过末尾可能存在的空格
                if (++j == n - 1) {
                    break;
                }
            }
        }
        digraph.getVertex(f).setFinal();
    }

    /**
     * 初始化匹配式，为后续构造nfa做准备
     *
     * @param regex 原匹配式
     * @return 修改后的匹配式
     */
    private static String initial(String regex) {
        StringBuilder tmp = new StringBuilder();
        int n = regex.length();
        char c;
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; ++i) {
            c = regex.charAt(i);
            if (c == '|' || c == '(') {
                stack.push(tmp.length());
                tmp.append(c);
                continue;
            }
            // 将A*这种匹配式改为(A)*，相当于插入了两个点
            if (i < n - 1 && regex.charAt(i + 1) == '*') {
                if (c != ')') {
                    tmp.append('(').append(c).append(')');
                } else {
                    // 将 (A|B)* 改为 ((A|B))*
                    if (tmp.charAt(stack.pop()) == '|') {
                        while (tmp.charAt(stack.peek()) == '|') {
                            stack.pop();
                        }
                        int left = stack.pop();
                        tmp.insert(left, '(');
                        tmp.append(c).append(')');
                    } else {
                        tmp.append(c);
                    }
                }
            } else if (c == ')') {
                if (tmp.charAt(stack.pop()) == '|') {
                    stack.pop();
                }
                tmp.append(c);
            } else {
                tmp.append(c);
            }
        }
        if (!stack.isEmpty()) {
            tmp.insert(0, '(');
            tmp.append(")");
        }
        return tmp.toString() + ' ';
    }

    String getRegex() {
        return regex;
    }

    int getS0() {
        return s0;
    }

    int getF() {
        return f;
    }

    Digraph getDigraph() {
        return digraph;
    }

    @Override
    public String toString() {
        return "\nNFA:\n"
                + "regex = \""
                + regex
                + '\"'
                + "\ns0 = "
                + s0
                + ", f = "
                + f
                + ", \nmove = {"
                + digraph
                + "\n}\n";
    }
}
